#include <iostream>
#include <stdlib.h>
#include <time.h>
#include "../include/swap.h"

using namespace std;

// 选择排序(从小到大)
// 1.以起始元素（ i = 0）为基准，设置为最小值，遍历一次，找到最小值，与起始元素交换。
// 2.循环执行上述步骤，从后一个元素开始（i + 1）为基准，设置为最小值，遍历一次,找到最小值，与起始元素交换。
// 3.执行完成后，排序完成。


// 时间和空间复杂度
// 时间复杂度：O(n^2)
// 平均时间复杂度：O(n^2)
// 空间复杂度：O(1)
// 最优时间复杂度：O(n^2)  不论如何，每次都要和后面的值比对之后才能确定最小值
// 不稳定，可能造成键值对中相同键的单位顺序发生变化。

void ChoiceSort(int arr[], int len)
{
    for (size_t i = 0; i < len - 1; i++)
    {
        int min = arr[i];
        int k = i;
        for (int j = i + 1; j < len; j++)
        {
            if (arr[j] < min)
            {
                min = arr[j];
                k = j;
            }
        }
        // 每一次循环最多执行一次交换
        if (k != 0)
            swap(arr[i], arr[k]);
    }
}

// int main(int argc, const char** argv) {
//     int arr[10];
//     srand(time(NULL));
//     for (int i = 0; i < 10; i++) {
//         arr[i] = rand() % 100;
//         cout << arr[i] << " ";
//     }
//     cout << endl;

//     ChoiceSort(arr, 10);
//     for (int val : arr)
//         cout << val << " ";
//     cout << endl;
//     return 0;
// }